import java.util.Stack;

public class StackPushPopValidator {

    /**
     * 验证弹出序列是否合法
     * @param pushSequence 压入序列
     * @param popSequence 弹出序列
     * @return 如果弹出序列合法返回true，否则返回false
     */

    public boolean isPopOrderValid(int[] pushSequence, int[] popSequence) {
        Stack<Integer> stack = new Stack<>();
        int popIndex = 0;  // 跟踪弹出序列popSequence的当前位置

        for (int i = 0; i < pushSequence.length; i++) {
            stack.push(pushSequence[i]);  // 按顺序压入元素

            // 检查栈顶元素是否与弹出序列当前元素匹配
            // 条件1: popIndex未越界
            // 条件2: 栈不为空
            // 条件3: 栈顶元素等于popSequence当前元素
            while (popIndex < popSequence.length && !stack.empty()
                    && stack.peek() == popSequence[popIndex]) {
                stack.pop();  // 匹配则弹出栈顶元素
                popIndex++;    // 移动到弹出序列的下一个元素
            }
        }

        // 如果栈为空，说明所有元素都按popSequence的顺序正确弹出
        // 否则说明popSequence不是合法的弹出顺序
        return stack.empty();
    }
}
